Word ladder¶
Time: O(NxD); Space: O(D); medium
Notes:
N is length of string,
D is size of dictionary
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
Output: 0
Example 2:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”, “cog”]
Output: 5
Explanation:
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.
Example 3:
Input: beginWord = “a”, endWord = “c”, wordList =[“a”, “b”, “c”]
Output: 2
Explanation:
“a”->“c”
Notes:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
[5]:
class Solution1(object):
'''
BFS
'''
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
distance, cur, visited, lookup = 0, [beginWord], set([beginWord]), set(wordList)
while cur:
next_queue = []
for word in cur:
if word == endWord:
return distance + 1
for i in range(len(word)):
for j in 'abcdefghijklmnopqrstuvwxyz':
candidate = word[:i] + j + word[i + 1:]
if candidate not in visited and candidate in lookup:
next_queue.append(candidate)
visited.add(candidate)
distance += 1
cur = next_queue
return 0
[6]:
s = Solution1()
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
assert s.ladderLength(beginWord, endWord, wordList) == 0
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log", "cog"]
assert s.ladderLength(beginWord, endWord, wordList) == 5
beginWord = "a"
endWord = "c"
wordList =["a", "b", "c"]
assert s.ladderLength(beginWord, endWord, wordList) == 2